package main

import "fmt"

// SelectSort 选择排序：选择类排序算法： 不稳定算法
func SelectSort(list []int) {
	n := len(list)

	for i := 0; i < n - 1; i++ {
		// 每次从第 i 位开始，找到最小的元素放置到 i 位置
		min := list[i] // 最小数
		minIndex := i  // 最小数下标
		for j := i + 1; j < n; j++ {
			if list[j] < min {
				min = list[j]
				minIndex = j
			}
		}

		if i != minIndex {
			list[i], list[minIndex] = list[minIndex], list[i]
		}
	}
}

// SelectGoodSort 简单选择排序算法改进：
// 上面的算法需要从某个数开始，一直扫描到尾部，我们可以优化算法，使得复杂度减少一半。
// 我们每一轮，除了找最小数之外，还找最大数，然后分别和前面和后面的元素交换，这样循环次数减少一半
// 优化后的选择排序还是很慢，它很好理解，但是还是不建议在工程上使用。
func SelectGoodSort(list []int) {
	n := len(list)

	// 只需要循环一半即可
	for i := 0; i < n / 2; i++ {
		minIndex := i;  // 最小值下标
		maxIndex := i;  // 最大值下标

		// 在这一轮迭代中要找到最大值和最小值的下标
		for j := i + 1; j < n - i; j++ {
			// 找到最大值下标
			if list[j] > list[maxIndex] {
				maxIndex = j  // 这一轮这个值最大，直接continue
				continue
			}
			// 找到最小值下标
			if list[j] < list[minIndex] {
				minIndex = j
			}
		}

		if maxIndex == i && minIndex != n - 1 - i {
			// 如果最大值是开头的元素，而最小值不是最末尾的元素，先将最大值和末尾元素交换
			list[n - 1 - i], list[maxIndex] = list[maxIndex], list[n - 1 - i]
			// 然后最小值元素放在最开头
			list[i], list[minIndex] = list[minIndex], list[i]
		} else if maxIndex == i && minIndex == n - 1 - i {
			// 如果最大值在开头，最小值在结尾，直接交换
			list[minIndex], list[maxIndex] = list[maxIndex], list[minIndex]
		} else {
			// 先将最小值放在开头，再将最小值放到结尾
			list[i], list[minIndex] = list[minIndex], list[i]
			list[n - 1 - i], list[maxIndex] = list[maxIndex], list[n - 1 - i]
		}
	}
}

func main() {

	/*list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	SelectSort(list)
	fmt.Println(list)*/

	list := []int{5}
	SelectGoodSort(list)
	fmt.Println(list)
	list1 := []int{5, 9}
	SelectGoodSort(list1)
	fmt.Println(list1)
	list2 := []int{5, 9, 1}
	SelectGoodSort(list2)
	fmt.Println(list2)
	list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	SelectGoodSort(list3)
	fmt.Println(list3)
	list4 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6}
	SelectGoodSort(list4)
	fmt.Println(list4)
}















